Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

摘要

Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G neednot be connected or simple (i.e., free of multiple edges). We give three setsof coding schemes for G which all take O(m+n) time for encoding and decoding.Our schemes employ new properties of canonical orderings for planar graphs andnew techniques of processing strings of multiple types of parentheses. For applications that need to determine in O(1) time the adjacency of twonodes and the degree of a node, we use 2m+(5+1/k)n + o(m+n) bits for anyconstant k > 0 while the best previous bound by Munro and Raman is 2m+8n +o(m+n). If G is triconnected or triangulated, our bit count decreases to 2m+3n+ o(m+n) or 2m+2n + o(m+n), respectively. If G is simple, our bit count is(5/3)m+(5+1/k)n + o(n) for any constant k > 0. Thus, if a simple G is alsotriconnected or triangulated, then 2m+2n + o(n) or 2m+n + o(n) bits suffice,respectively. If only adjacency queries are supported, the bit counts for a general G and asimple G become 2m+(14/3)n + o(m+n) and (4/3)m+5n + o(n), respectively. If we only need to reconstruct G from its code, a simple and triconnected Guses roughly 2.38m + O(1) bits while the best previous bound by He, Kao, and Luis 2.84m.